package org.parngon.maze;

//import java.awt.Point;
import java.awt.Dimension;
import java.awt.Rectangle;

import java.io.IOException;
import java.util.Arrays;
import java.util.Vector;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Iterator;
import java.util.Random;

import java.text.DecimalFormat;

import org.parngon.common.Coord;

public class Maze<T extends Coord>
{
  public static final int DIR_TEND = 10;

  public static final int TOP = 1;
  public static final int BOTTOM = 2;
  public static final int LEFT = 4;
  public static final int RIGHT = 8;

  static DecimalFormat dFormat = new DecimalFormat("0.00");

  int col, row;
  Tile<T> maze[][] = null;

  boolean wbpSet = false;
  double wallBreakingP = 0.3;
  boolean dfpSet = false;
  double deadendFillingP = 0.0;

  Vector<RectangularArea> patts = new Vector<RectangularArea>();

  Vector<Tile<T>> ll = new Vector<Tile<T>>();
  Vector<Tile<T>> tmpLL = new Vector<Tile<T>>();
  long seed = 0;
  Random rand = null;

  LinkedList<MazeListener> listeners = new LinkedList<MazeListener>();
  String status = null;

  boolean debug = false;

  public Maze()
  {
  }

  public void setCol(int c)
  {
    if ( c <= 0 ) throw new RuntimeException("Invalid dimension");

    col = c;
  }

  public void setRow(int r)
  {
    if ( r <= 0 ) throw new RuntimeException("Invalid dimension");

    row = r;
  }

  public Maze(int c, int r)
  {
    if ( c <= 0 || r <= 0 ) throw new RuntimeException("Invalid dimension");

    col = c;
    row = r;

    setSeed(System.currentTimeMillis());
  }

  public void setSeed(long s)
  {
    seed = s;
    rand = new Random(s);
  }

  public long getSeed()
  {
    return seed;
  }

  public void addPattern(RectangularArea ra)
  {
    patts.add(ra);
  }

  public void generate(long s)
  {
    setSeed(s);
    generate();
  }

  public void setWallBreakingPercentage(double wbp)
  {
    wbpSet = true;
    wallBreakingP = wbp;
  }

  public void setDeadendFillingPercentage(double dfp)
  {
    dfpSet = true;
    deadendFillingP = dfp;
  }

  public void generate()
  {
    long t0 = System.currentTimeMillis();

    ll.clear();
    tmpLL.clear();

    maze = new Tile[row][col];

    for ( int i = 0; i < row; i++ ) {
      for ( int ii = 0; ii < col; ii++ ) {
        maze[i][ii] = new Tile(ii, i, this);
        // connecting them together
        if ( i > 0 ) {
          maze[i][ii].top = maze[i - 1][ii];
          maze[i - 1][ii].bottom = maze[i][ii];
        }
        if ( ii > 0 ) {
          maze[i][ii].left = maze[i][ii - 1];
          maze[i][ii - 1].right = maze[i][ii];
        }
      }
    }

    for ( int i = 0; i < row; i++ ) {
      maze[i][0].leftWall(true);
      maze[i][col - 1].rightWall(true);
    }

    for ( int i = 0; i < col; i++ ) {
      maze[0][i].topWall(true);
      maze[row - 1][i].bottomWall(true);
    }

    for ( RectangularArea ra: patts ) {
      if ( ra.getType() == RectangularArea.BLOCK ) {
        createRectangularBlock(ra.getBounds());
      } else if ( ra.getType() == RectangularArea.VOID ) {
        createRectangularVoid(ra.getBounds());
      }
    }

    int sx = rand.nextInt(col);
    int sy = rand.nextInt(row);

    System.out.println("start: " + sx + "," + sy);

    Tile<T> start = maze[sy][sx];
    while ( start.isCarved() ) {
      sx = rand.nextInt(col);
      sy = rand.nextInt(row);
      System.out.println("start: " + sx + "," + sy);
      start = maze[sy][sx];
    }
    start.carve();
    start.topWall(true);
    start.bottomWall(true);
    start.leftWall(true);
    start.rightWall(true);
    /*
    */

    ll.add(start);

    Tile<T> neighbours[] = new Tile[4];
    char directions[] = new char[4];
    int weights[] = new int[4];
    int nrNeighbours = 0;
    while ( ll.size() > 0 ) {
      int llSize = ll.size();
      /*
      // random through the list
      Tile pt = ll.remove(rand.nextInt(llSize));
      */

      /*
      // only the last tile
      Tile pt = ll.remove(llSize - 1);
      */

      /*
      // only the last two tiles
      boolean secondLast = llSize > 1 ? rand.nextBoolean() : false;
      Tile pt = ll.remove(secondLast ? llSize - 2 : llSize - 1);
      */

      /*
      // closer to tail = larger chances
      int tileWeights[] = new int[llSize];
      for ( int i = 0; i < llSize; i++ ) {
        tileWeights[i] = (i + 1) * (i + 1) * (i + 1);
      }
      Tile pt = ll.remove(weightedRandom(tileWeights));
      */

      // tails with larger chances
      int tileWeights[] = new int[llSize];
      Arrays.fill(tileWeights, 1);
      tileWeights[llSize - 1] = 10000;
      if ( llSize > 1 ) tileWeights[llSize - 2] = 1000;
      if ( llSize > 2 ) tileWeights[llSize - 3] = 100;
      if ( llSize > 3 ) tileWeights[llSize - 4] = 10;
      Tile<T> pt = ll.remove(weightedRandom(tileWeights));
      /*
      */

      /*
      // heads and tails with larger chances
      int tileWeights[] = new int[llSize];
      Arrays.fill(tileWeights, 0);
      if ( llSize > 2 ) {
        int halfList = llSize / 2;
        int maxCandidatesPerHead = 3;
        for ( int i = 0; i < halfList && i < maxCandidatesPerHead; i++ ) {
          tileWeights[i] = tileWeights[llSize - i - 1] = (int)Math.pow(10, maxCandidatesPerHead - i - 1);
        }
      }
      Tile pt = ll.remove(weightedRandom(tileWeights));
      */

      /*
      // tails with larger chances (log)
      double tileWeights[] = new double[llSize];
      for ( int i = 0; i < llSize; i++ ) {
        tileWeights[i] = Math.log10(i + 1);
      }
      Tile pt = ll.remove(weightedRandom(tileWeights));
      */

      /*
      // heads and tails with larger chances (log)
      double tileWeights[] = new double[llSize];
      Arrays.fill(tileWeights, 0);
      if ( llSize > 2 ) {
        int halfList = llSize / 2;
        int maxCandidatesPerHead = 5;
        for ( int i = 0; i < halfList && i < maxCandidatesPerHead; i++ ) {
          tileWeights[i] = tileWeights[llSize - i - 1] = Math.log10(maxCandidatesPerHead - i);
        }
      }
      Tile pt = ll.remove(weightedRandom(tileWeights));
      */

      /*
      // ???
      Tile pt = ll.remove(llSize / 2);
      */

      // check the neighbour
      nrNeighbours = 0;
      if ( pt.top != null && !pt.top.isCarved() ) {
        weights[nrNeighbours] = !pt.hasBottomWall() ? DIR_TEND : 1;
        directions[nrNeighbours] = 'T';
        neighbours[nrNeighbours++] = pt.top;
      }
      if ( pt.bottom != null && !pt.bottom.isCarved() ) {
        weights[nrNeighbours] = !pt.hasTopWall() ? DIR_TEND : 1;
        directions[nrNeighbours] = 'B';
        neighbours[nrNeighbours++] = pt.bottom;
      }
      if ( pt.left != null && !pt.left.isCarved() ) {
        weights[nrNeighbours] = !pt.hasRightWall() ? DIR_TEND : 1;
        directions[nrNeighbours] = 'L';
        neighbours[nrNeighbours++] = pt.left;
      }
      if ( pt.right != null && !pt.right.isCarved() ) {
        weights[nrNeighbours] = !pt.hasLeftWall() ? DIR_TEND : 1;
        directions[nrNeighbours] = 'R';
        neighbours[nrNeighbours++] = pt.right;
      }

      if ( nrNeighbours > 0 ) {
        //int chosen = rand.nextInt(nrNeighbours);
        int chosen = weightedRandom(weights, nrNeighbours);
        Tile<T> ct = neighbours[chosen];
        char cd = directions[chosen];

        ct.carve();
        ct.topWall(true);
        ct.bottomWall(true);
        ct.leftWall(true);
        ct.rightWall(true);

        // connect this with the picked tile
        switch ( cd ) {
          case 'T':
            ct.bottomWall(false);
            break;
          case 'B':
            ct.topWall(false);
            break;
          case 'L':
            ct.rightWall(false);
            break;
          case 'R':
            ct.leftWall(false);
            break;
        }

        tmpLL.clear();
        tmpLL.addAll(ll);
        for ( Tile<T> aTile: ll )
          if ( aTile.getNumberOfUncarvedNeighbours() == 0 )
            tmpLL.remove(aTile);
        ll.clear();
        ll.addAll(tmpLL);
/*
*/
        if ( pt.getNumberOfUncarvedNeighbours() > 0 ) ll.add(pt);
        if ( ct.getNumberOfUncarvedNeighbours() > 0 ) ll.add(ct);

        if ( debug ) {
          System.out.println("(" + pt.y + "," + pt.x + ") " + cd + " (" + ct.y + "," + ct.x + ") " + ll.size());
          System.out.print(this);
          try {
            Thread.sleep(10);
          } catch ( InterruptedException ie ) {
          }
        }
      }
    }

    for ( int i = 0; i < row; i++ ) {
      for ( int ii = 0; ii < col; ii++ ) {
        maze[i][ii].mark(false);
      }
    }

    long t1 = System.currentTimeMillis();
    System.out.println("generate(): " + dFormat.format((t1 - t0) / 1000.0));

    if ( wbpSet ) {
      _breakWalls(wallBreakingP);
    }

    if ( dfpSet ) {
      _fillDeadends(deadendFillingP);
    }

    MazeEvent me = new MazeEvent(this, createMessage());
    fireMazeChanged(me);
  }

  public synchronized void addMazeListener(MazeListener ml)
  {
    listeners.add(ml);
  }

  public synchronized void removeMazeListener(MazeListener ml)
  {
    listeners.remove(ml);
  }

  private synchronized void fireMazeChanged(MazeEvent me)
  {
    for ( MazeListener aML: listeners ) aML.mazeChanged(me);
  }

  public void setDebug(boolean d)
  {
    debug = d;
  }

  public Vector<Tile<T>> getDeadends()
  {
    Vector<Tile<T>> vdes = new Vector<Tile<T>>();

    for ( int i = 0; i < maze.length; i++ )
      for ( int ii = 0; ii < maze[i].length; ii++ )
        if ( maze[i][ii].isDeadend() )
          vdes.add(maze[i][ii]);

    return vdes;
  }

  private boolean _fillDeadend(Tile<T> d)
  {
    if ( d == null || !d.isDeadend() ) return false;

    Vector<Tile<T>> path = new Vector<Tile<T>>();

    d.mark(true);

    path.add(d);

    Tile<T> n = null;

    if ( !d.hasTopWall() ) {
      n = d.top;
    } else if ( !d.hasBottomWall() ) {
      n = d.bottom;
    } else if ( !d.hasLeftWall() ) {
      n = d.left;
    } else if ( !d.hasRightWall() ) {
      n = d.right;
    }

    while ( n != null ) {
      if ( n.getNumberOfNeighbours() == 1 || n.getNumberOfNeighbours() == 2 ) {
        n.mark(true);
        path.add(n);
        if ( !n.hasTopWall() && n.top != null && !n.top.isMarked() ) {
          n = n.top;
        } else if ( !n.hasBottomWall() && n.bottom != null && !n.bottom.isMarked() ) {
          n = n.bottom;
        } else if ( !n.hasLeftWall() && n.left != null && !n.left.isMarked() ) {
          n = n.left;
        } else if ( !n.hasRightWall() && n.right != null && !n.right.isMarked() ) {
          n = n.right;
        } else {
          n = null;
        }
      } else {
        n = null;
      }
    }

    //System.out.println("path: " + path);
    for ( Tile<T> p: path ) {
      p.brick();
//      if ( p.top != null ) p.top.bottomWall(true);
//      if ( p.bottom != null ) p.bottom.topWall(true);
//      if ( p.left != null ) p.left.rightWall(true);
//      if ( p.right != null ) p.right.leftWall(true);
      p.mark(false);
    }

    return true;
  }

  private boolean _fillDeadends(double perc)
  {
    boolean result = false;

    if ( perc < 0.0 || perc > 1.0 ) return false;

    Vector<Tile<T>> deadends = getDeadends();

    int max = (int)(deadends.size() * perc);

    for ( int i = 0; i < max && deadends.size() > 0; i++ ) {
      Tile<T> dd = deadends.remove(rand.nextInt(deadends.size()));
      result = _fillDeadend(dd) || result;
    }

    return result;
  }

  public boolean fillDeadend(Tile<T> d)
  {
    boolean result = _fillDeadend(d);

    if ( result ) {
      MazeEvent me = new MazeEvent(this, createMessage());
      fireMazeChanged(me);
    }

    return result;
  }

  public boolean fillDeadends(double perc)
  {
    boolean result = _fillDeadends(perc);

    if ( result ) {
      MazeEvent me = new MazeEvent(this, createMessage());
      fireMazeChanged(me);
    }

    return result;
  }

  private int weightedRandom(int weights[], int nrWeights)
  {
    int result = -1;
    long total = 0;

    for ( int i = 0; i < nrWeights; i++ ) total += weights[i];

    long srand = (long)(rand.nextDouble() * total);
    for ( int i = 0; i < nrWeights && result == -1; i++ ) {
      srand -= weights[i];
      if ( srand <= 0 ) result = i;
    }

    if ( result == -1 ) result = nrWeights - 1;

    return result;
  }

  private int weightedRandom(int weights[])
  {
    /*
    for ( int w: weights )
      System.out.print(w + " ");
    System.out.println();
    */
    return weightedRandom(weights, weights.length);
  }

  private int weightedRandom(double weights[], int nrWeights)
  {
    int result = -1;
    double total = 0;

    for ( int i = 0; i < nrWeights; i++ ) total += weights[i];

    double srand = rand.nextDouble() * total;
    for ( int i = 0; i < nrWeights && result == -1; i++ ) {
      srand -= weights[i];
      if ( srand <= 0 ) result = i;
    }

    if ( result == -1 ) result = nrWeights - 1;

    return result;
  }

  private int weightedRandom(double weights[])
  {
    /*
    boolean dotted = false;
    for ( double w: weights ) {
      if ( w == 0.0 ) {
        if ( !dotted ) {
          dotted = true;
          System.out.print("... ");
        }
      } else {
        System.out.print(((float)w) + " ");
      }
    }
    System.out.println();
    */
    return weightedRandom(weights, weights.length);
  }

  public DeadendPair<T> getFurtherestDeadendPair()
  {
    Vector<Tile<T>> deadends = getDeadends();

    if ( deadends.size() < 2 ) return null;

    DeadendPair<T> result = null;
    double fdpd = 0;

    for ( int i = 0; i < deadends.size(); i++ ) {
      Tile<T> s = deadends.elementAt(i);
      for ( int ii = i + 1; ii < deadends.size(); ii++ ) {
        Tile<T> e = deadends.elementAt(ii);
        DeadendPair dp = new DeadendPair(s, e);
        if ( dp.getDistance() > fdpd ) {
          fdpd = dp.getDistance();
          result = dp;
        }
      }
    }

    return result;
  }

  public DeadendPair<T> deadendsDistance()
  {
    Vector<Tile<T>> deadends = getDeadends();

    if ( debug ) System.out.println("Number of deadends: " + deadends.size());

    if ( deadends.size() < 2 ) return null;

    Vector<DeadendPair> vdps = new Vector<DeadendPair>();
    for ( int i = 0; i < deadends.size(); i++ ) {
      for ( int ii = i + 1; ii < deadends.size(); ii++ ) {
        Tile<T> s = deadends.elementAt(i);
        Tile<T> e = deadends.elementAt(ii);
        vdps.add(new DeadendPair(s, e));
      }
    }

    if ( debug ) System.out.println("Number of deadend pairs: " + vdps.size());

    int idx = 0;
    DeadendPair<T> dps[] = new DeadendPair<T>[vdps.size()];
    for ( DeadendPair<T> aPair: vdps ) dps[idx++] = aPair;
    FlashSort.flashsort(dps);

    if ( dps != null && dps.length > 0 ) {
      DeadendPair<T> result = dps[dps.length - 1];

      if ( debug ) System.out.println(result.getStart() + " - " + result.getEnd() + " " + result.getDistance());

      return result;
    }

    return null;
  }

  private boolean _breakWall(Tile<T> a, Tile<T> b)
  {
    if ( a == null || b == null || a.getNeighbourDirection(b) == -1 || a.isBrick() || b.isBrick() ) return false;

    //System.out.println("break wall between " + a + " and " + b);
    int d = a.getNeighbourDirection(b);
    switch ( d ) {
      case TOP:
        a.topWall(false);
        break;
      case BOTTOM:
        a.bottomWall(false);
        break;
      case LEFT:
        a.leftWall(false);
        break;
      case RIGHT:
        a.rightWall(false);
        break;
    }

    return true;
  }

  private boolean _breakWalls(double perc)
  {
    boolean result = false;

    if ( perc < 0.0 || perc > 1.0 ) return false;

    Vector<Tile<T>> deadends = getDeadends();

    int max = (int)(deadends.size() * perc);

    for ( int i = 0; i < max && deadends.size() > 0; i++ ) {
      Tile<T> dt = deadends.remove(rand.nextInt(deadends.size()));
      Tile<T> nt = dt.getRandomDisconnectedNeighbour();
      if ( nt != null ) {
        result = _breakWall(dt, nt) || result;
      }
    }

    return result;
  }

  private boolean _buildWall(Tile<T> a, Tile<T> b)
  {
    if ( a == null || b == null || a.getNeighbourDirection(b) == -1 || a.isBrick() || b.isBrick() ) return false;

    //System.out.println("build wall between " + a + " and " + b);
    int d = a.getNeighbourDirection(b);
    switch ( d ) {
      case TOP:
        a.topWall(true);
        break;
      case BOTTOM:
        a.bottomWall(true);
        break;
      case LEFT:
        a.leftWall(true);
        break;
      case RIGHT:
        a.rightWall(true);
        break;
    }

    return true;
  }

  
  public boolean buildWall(Tile<T> a, Tile<T> b)
  {
    boolean result = _buildWall(a, b);

    if ( result ) {
      MazeEvent me = new MazeEvent(this, createMessage());
      fireMazeChanged(me);
    }

    return result;
  }

  public boolean breakWall(Tile<T> a, Tile<T> b)
  {
    boolean result = _breakWall(a, b);

    if ( result ) {
      MazeEvent me = new MazeEvent(this, createMessage());
      fireMazeChanged(me);
    }

    return result;
  }

  public boolean breakWalls(double perc)
  {
    boolean result = _breakWalls(perc);

    if ( result ) {
      MazeEvent me = new MazeEvent(this, createMessage());
      fireMazeChanged(me);
    }

    return result;
  }

  public Tile<T> getTile(int x, int y)
  {
    if ( x < 0 || y < 0 || x >= col || y >= row ) return null;

    return maze[y][x];
  }
/*
  public Tile getTile(Point loc)
  {
    if ( loc.x < 0 || loc.y < 0 || loc.x >= col || loc.y >= row ) return null;

    return maze[loc.y][loc.x];
  }
*/
  public Tile<T> getTile(T loc)
  {
    if ( loc.x < 0 || loc.y < 0 || loc.x >= col || loc.y >= row ) return null;

    return maze[loc.y][loc.x];
  }

  private String createMessage()
  {
    int dsz = getDeadends().size();

    StringBuffer sb = new StringBuffer("Number of deadends:");
    sb.append(dsz).append("(").append(dFormat.format(dsz * 100.0 / (row * col))).append("%)");

    return sb.toString();
  }

/*
  public void createRectangularVoid()
  {
    int x1 = rand.nextInt(col - 2);
    int y1 = rand.nextInt(row - 2);
    int rw = rand.nextInt(col / 4) + 2;
    int rh = rand.nextInt(row / 4) + 2;
    int x2 = x1 + rw > col - 1 ? col - 1 : x1 + rw - 1;
    int y2 = y1 + rh > row - 1 ? row - 1 : y1 + rh - 1;

    System.out.println("original size = " + rw + "x" + rh);
    System.out.println("creating void at (" + x1 + "," + y1 + ") size = " + (x2 - x1 + 1) + "x" + (y2 - y1 + 1));
    System.out.println("bounds = (" + x1 + "," + y1 + ") => (" + x2 + "," + y2 +")");

    for ( int i = x1; i <= x2; i++ ) {
      maze[y1][i].bottomWall(false);
      maze[y2][i].topWall(false);
      if ( i > x1 && i <= x2 - 1 ) {
        maze[y1][i].leftWall(false);
        maze[y1][i].rightWall(false);
        maze[y2][i].leftWall(false);
        maze[y2][i].rightWall(false);
      }
    }

    for ( int i = y1; i <= y2; i++ ) {
      maze[i][x1].rightWall(false);
      maze[i][x2].leftWall(false);
      if ( i > y1 && i <= y2 - 1 ) {
        maze[i][x1].topWall(false);
        maze[i][x1].bottomWall(false);
        maze[i][x2].topWall(false);
        maze[i][x2].bottomWall(false);
      }
    }

    for ( int i = y1 + 1; i <= y2 - 1; i++ ) {
      for ( int ii = x1 + 1; ii <= x2 - 1; ii++ ) {
        Tile t = maze[i][ii];
        t.topWall(false);
        t.bottomWall(false);
        t.leftWall(false);
        t.rightWall(false);
      }
    }
  }
*/

  public void createRectangularBlock(Rectangle r)
  {
    int x1 = r.getLocation().x;
    int y1 = r.getLocation().y;
    int x2 = x1 + r.getSize().width - 1;
    int y2 = y1 + r.getSize().height - 1;

    maze[y1][x1].carve();
    maze[y1][x1].brick();
    if ( maze[y1][x1].top != null ) maze[y1][x1].top.bottomWall(true);
    if ( maze[y1][x1].left != null ) maze[y1][x1].left.rightWall(true);
    //maze[y1][x1].mark(1);

    maze[y1][x2].carve();
    maze[y1][x2].brick();
    if ( maze[y1][x2].top != null ) maze[y1][x2].top.bottomWall(true);
    if ( maze[y1][x2].right != null ) maze[y1][x2].right.leftWall(true);
    //maze[y1][x2].mark(1);

    maze[y2][x1].carve();
    maze[y2][x1].brick();
    if ( maze[y2][x1].bottom != null ) maze[y2][x1].bottom.topWall(true);
    if ( maze[y2][x1].left != null ) maze[y2][x1].left.rightWall(true);
    //maze[y2][x1].mark(1);

    maze[y2][x2].carve();
    maze[y2][x2].brick();
    if ( maze[y2][x2].bottom != null ) maze[y2][x2].bottom.topWall(true);
    if ( maze[y2][x2].right != null ) maze[y2][x2].right.leftWall(true);
    //maze[y2][x2].mark(1);

    for ( int i = x1 + 1; i < x2; i++ ) {
      maze[y1][i].carve();
      maze[y1][i].brick();
      if ( maze[y1][i].top != null ) maze[y1][i].top.bottomWall(true);
      //maze[y1][i].mark(2);

      maze[y2][i].carve();
      maze[y2][i].brick();
      if ( maze[y2][i].bottom != null ) maze[y2][i].bottom.topWall(true);
      //maze[y2][i].mark(2);
    }

    for ( int i = y1 + 1; i < y2; i++ ) {
      maze[i][x1].carve();
      maze[i][x1].brick();
      if ( maze[i][x1].left != null ) maze[i][x1].left.rightWall(true);
      //maze[i][x1].mark(2);

      maze[i][x2].carve();
      maze[i][x2].brick();
      if ( maze[i][x2].right != null ) maze[i][x2].right.leftWall(true);
      //maze[i][x2].mark(2);
    }

    for ( int i = y1 + 1; i < y2; i++ ) {
      for ( int ii = x1 + 1; ii < x2; ii++ ) {
        maze[i][ii].carve();
        maze[i][ii].brick();
        //maze[i][ii].mark(3);
      }
    }
/*
    for ( int i = y1; i < y2; i++ ) {
      for ( int ii = x1; ii < x2; ii++ ) {
        maze[i][ii].carve();
        maze[i][ii].brick();
      }
    }
*/
  }

  public void createRectangularVoid(Rectangle r)
  {
    int x1 = r.getLocation().x;
    int y1 = r.getLocation().y;
    int x2 = x1 + r.getSize().width - 1;
    int y2 = y1 + r.getSize().height - 1;

    for ( int i = y1; i <= y2; i++ ) {
      for ( int ii = x1; ii <= x2; ii++ ) {
        maze[i][ii].carve();
        maze[i][ii].topWall(false);
        maze[i][ii].bottomWall(false);
        maze[i][ii].leftWall(false);
        maze[i][ii].rightWall(false);
        maze[i][ii].mark(4);
      }
    }

    if ( maze[y1][x1].top == null || maze[y1][x1].top.getMark() != 4 ) {
      maze[y1][x1].topWall(true);
    }
    if ( maze[y1][x1].left == null || maze[y1][x1].left.getMark() != 4 ) {
      maze[y1][x1].leftWall(true);
    }
    //maze[y1][x1].mark(1);

    if ( maze[y1][x2].top == null || maze[y1][x2].top.getMark() != 4 ) {
      maze[y1][x2].topWall(true);
    }
    if ( maze[y1][x2].right == null || maze[y1][x2].right.getMark() != 4 ) {
      maze[y1][x2].rightWall(true);
    }
    //maze[y1][x2].mark(1);

    if ( maze[y2][x1].bottom == null || maze[y2][x1].bottom.getMark() != 4 ) {
      maze[y2][x1].bottomWall(true);
    }
    if ( maze[y2][x1].left == null || maze[y2][x1].left.getMark() != 4 ) {
      maze[y2][x1].leftWall(true);
    }
    //maze[y2][x1].mark(1);

    if ( maze[y2][x2].bottom == null || maze[y2][x2].bottom.getMark() != 4 ) {
      maze[y2][x2].bottomWall(true);
    }
    if ( maze[y2][x2].right == null || maze[y2][x2].right.getMark() != 4 ) {
      maze[y2][x2].rightWall(true);
    }
    //maze[y2][x2].mark(1);

    for ( int i = x1 + 1; i < x2; i++ ) {
      if ( maze[y1][i].top == null || maze[y1][i].top.getMark() != 4 ) {
        maze[y1][i].topWall(true);
      }
      //maze[y1][i].mark(2);

      if ( maze[y2][i].bottom == null || maze[y2][i].bottom.getMark() != 4 ) {
        maze[y2][i].bottomWall(true);
      }
      //maze[y2][i].mark(2);
    }

    for ( int i = y1 + 1; i < y2; i++ ) {
      if ( maze[i][x1].left == null || maze[i][x1].left.getMark() != 4 ) {
        maze[i][x1].leftWall(true);
      }
      //maze[i][x1].mark(2);

      if ( maze[i][x2].right == null || maze[i][x2].right.getMark() != 4 ) {
        maze[i][x2].rightWall(true);
      }
      //maze[i][x2].mark(2);
    }
/*
    for ( int i = y1 + 1; i < y2; i++ ) {
      for ( int ii = x1 + 1; ii < x2; ii++ ) {
        maze[i][ii].carve();
        maze[i][ii].topWall(false);
        maze[i][ii].bottomWall(false);
        maze[i][ii].leftWall(false);
        maze[i][ii].rightWall(false);
        //maze[i][ii].mark(3);
      }
    }
*/
  }

/*
  public void createRectangularBlock()
  {
    int x1 = rand.nextInt(col - 2);
    int y1 = rand.nextInt(row - 2);
    int rw = rand.nextInt(col / 4) + 2;
    int rh = rand.nextInt(row / 4) + 2;
    int x2 = x1 + rw > col - 1 ? col - 1 : x1 + rw - 1;
    int y2 = y1 + rh > row - 1 ? row - 1 : y1 + rh - 1;

    System.out.println("original size = " + rw + "x" + rh);
    System.out.println("creating block at (" + x1 + "," + y1 + ") size = " + (x2 - x1 + 1) + "x" + (y2 - y1 + 1));
    System.out.println("bounds = (" + x1 + "," + y1 + ") => (" + x2 + "," + y2 +")");

    for ( int i = y1; i <= y2; i++ ) {
      for ( int ii = x1; ii <= x2; ii++ ) {
        maze[i][ii].brick();
        maze[i][ii].mark(true);
      }
    }

    for ( int i = x1; i <= x2; i++ ) {
      Tile tt = maze[y1][i];
      if ( tt.top != null ) {
        tt.top.bottomWall(true);
//        fillDeadend(tt.top);
      }
      Tile bt = maze[y2][i];
      if ( bt.bottom != null ) {
        bt.bottom.topWall(true);
//        fillDeadend(tt.bottom);
      }
    }

    for ( int i = y1; i <= y2; i++ ) {
      Tile lt = maze[i][x1];
      if ( lt.left != null ) lt.left.rightWall(true);
      Tile rt = maze[i][x2];
      if ( rt.right != null ) rt.right.leftWall(true);
    }
  }
*/

  public String toString()
  {
    if ( debug ) {
      char text[][] = new char[maze.length * 2 + 1][maze[0].length * 2 + 1];

      for ( int i = 0; i < text.length; i++ ) {
        for ( int ii = 0; ii < text[i].length; ii++ ) {
          text[i][ii] = '.';
        }
      }

      for ( int i = 0; i < maze.length; i++ ) {
        for ( int ii = 0; ii < maze[i].length; ii++ ) {
          if ( maze[i][ii].isBrick() ) {
            text[i * 2][ii * 2] = 'X';
            text[i * 2][ii * 2 + 1] = 'X';
            text[i * 2][ii * 2 + 2] = 'X';
            text[i * 2 + 1][ii * 2] = 'X';
            text[i * 2 + 1][ii * 2 + 1] = 'X';
            text[i * 2 + 1][ii * 2 + 2] = 'X';
            text[i * 2 + 2][ii * 2] = 'X';
            text[i * 2 + 2][ii * 2 + 1] = 'X';
            text[i * 2 + 2][ii * 2 + 2] = 'X';
          } else {
            if ( maze[i][ii].isCarved() ) {
              text[i * 2 + 1][ii * 2 + 1] = '.';
              text[i * 2][ii * 2 + 1] = '.';
              text[i * 2 + 2][ii * 2 + 1] = '.';
              text[i * 2 + 1][ii * 2] = '.';
              text[i * 2 + 1][ii * 2 + 2] = '.';
            }
            if ( maze[i][ii].hasTopWall() ) {
              text[i * 2][ii * 2] = 'X';
              text[i * 2][ii * 2 + 1] = 'X';
              text[i * 2][ii * 2 + 2] = 'X';
            }
            if ( maze[i][ii].hasBottomWall() ) {
              text[i * 2 + 2][ii * 2] = 'X';
              text[i * 2 + 2][ii * 2 + 1] = 'X';
              text[i * 2 + 2][ii * 2 + 2] = 'X';
            }
            if ( maze[i][ii].hasLeftWall() ) {
              text[i * 2][ii * 2] = 'X';
              text[i * 2 + 1][ii * 2] = 'X';
              text[i * 2 + 2][ii * 2] = 'X';
            }
            if ( maze[i][ii].hasRightWall() ) {
              text[i * 2][ii * 2 + 2] = 'X';
              text[i * 2 + 1][ii * 2 + 2] = 'X';
              text[i * 2 + 2][ii * 2 + 2] = 'X';
            }
          }
        }
      }

      StringBuffer result = new StringBuffer();

      result.append("  ");
      for ( int i = 0; i < text[0].length / 2; i++ ) result.append(" " + (i % 10));
      result.append('\n');

      for ( int i = 0; i < text.length; i++ ) {
        if ( i % 2 == 0 )
          result.append("  ");
        else
          result.append(" " + ((i / 2) % 10));
        for ( int ii = 0; ii < text[i].length; ii++ ) {
          result.append(text[i][ii]);
        }
        result.append('\n');
      }

      return result.toString();
    } else {
      return "Maze-" + col + "x" + row + "@" + hashCode();
    }
  }
/*
  public int getDistance(Point src, Point dst)
  {
    return Math.abs(src.x - dst.x) + Math.abs(src.y - dst.y);
  }
*/
  public int getDistance(T src, T dst)
  {
    return Math.abs(src.x - dst.x) + Math.abs(src.y - dst.y);
  }

/*
  public double getStraightLineDistance(Point src, Point dst)
  {
    return Math.sqrt(Math.pow((src.x - dst.x), 2) + Math.pow((src.y - dst.y), 2));
  }
*/
  public double getStraightLineDistance(T src, T dst)
  {
    return Math.sqrt(Math.pow((src.x - dst.x), 2) + Math.pow((src.y - dst.y), 2));
  }

/*
  public double getFudgeHeuristicCost(Point src, Point dst)
  {
    double dx1 = src.x - dst.x;
    double dy1 = src.y - dst.y;
    double dx2 = -dst.x;
    double dy2 = -dst.y;
    double cross = dx1 * dy2 - dx2 * dy1;

    return Math.abs(dx1) + Math.abs(dy1) + Math.abs(cross) * 0.0002;
  }
*/
  public double getFudgeHeuristicCost(T src, T dst)
  {
    double dx1 = src.x - dst.x;
    double dy1 = src.y - dst.y;
    double dx2 = -dst.x;
    double dy2 = -dst.y;
    double cross = dx1 * dy2 - dx2 * dy1;

    return Math.abs(dx1) + Math.abs(dy1) + Math.abs(cross) * 0.0002;
  }

/*
  public double getHeuristicCost(AStarNode<T> from, AStarNode<T> goal)
  {
    //Point s = from.getLocation();
    //Point e = goal.getLocation();

    //return getStraightLineDistance(s, e);
    return getFudgeHeuristicCost(s, e);
  }
*/
  public double getHeuristicCost(Tile<T> from, Tile<T> goal)
  {
    T s = from.getLocation();
    T e = goal.getLocation();

    //return getStraightLineDistance(s, e);
    return getFudgeHeuristicCost(s, e);
  }

/*
  public double getTerrainCost(AStarNode from, AStarNode to)
  {
    Point fromLoc = from.getLocation();
    Point toLoc = to.getLocation();

    Tile ft = maze[fromLoc.y][fromLoc.x];
    Tile tt = maze[toLoc.y][toLoc.x];

    if ( ft.isConnectedNeighbour(tt) ) {
      return 1;
    }

    return Double.POSITIVE_INFINITY;
  }
*/
  public double getTerrainCost(Tile<T> from, Tile<T> to)
  {
    T fromLoc = from.getLocation();
    T toLoc = to.getLocation();

    Tile<T> ft = maze[fromLoc.y][fromLoc.x];
    Tile<T> tt = maze[toLoc.y][toLoc.x];

    if ( ft.isConnectedNeighbour(tt) ) {
      return 1;
    }

    return Double.POSITIVE_INFINITY;
  }

/*
  public ArrayList <AStarNode<T>>getNeighbours(AStarNode target)
  {
    Point asp = target.getLocation();

    ArrayList <AStarNode>result = new ArrayList<AStarNode>();
    Tile ns[] = maze[asp.y][asp.x].getConnectedNeighbours();
    for ( Tile aTile: ns ) result.add(aTile);

    return result;
  }
*/
  public ArrayList<Tile<T>> getNeighbours(Tile<T> target)
  {
    T asp = target.getLocation();

    ArrayList<Tile<T>> result = new ArrayList<Tile<T>>();
    Tile<T> ns[] = maze[asp.y][asp.x].getConnectedNeighbours();
    for ( Tile<T> aTile: ns ) result.add(aTile);

    return result;
  }

  public int getWidth()
  {
    return maze[0].length;
  }

  public int getHeight()
  {
    return maze.length;
  }

  public Dimension getSize()
  {
    return new Dimension(maze[0].length, maze.length);
  }

  public static void main(String argv[])
  {
    Maze<Co2D> maze = new Maze<Co2D>(Integer.valueOf(argv[0]), Integer.valueOf(argv[1]));

    maze.setDebug(true);
    maze.generate();

    System.out.println(maze);
    System.out.println("Before breaking walls, number of deadends = " + maze.getDeadends().size());

//    maze.createRectangularVoid();
//    System.out.println(maze);

//    maze.breakWalls(0.3);
//    System.out.println(maze);

//    maze.fillDeadends(0.8);
//    System.out.println(maze);

    DeadendPair<Co2D> dp = maze.getFurtherestDeadendPair();

    if ( dp != null ) {
      AStar<Co2D> as = new AStar<Co2D>();
      System.out.println(as.findPath(dp.getStart(), dp.getEnd(), maze));
    }
  }
}
